#include<iostream>
#include<cmath>
using namespace std;
int main ()
{
    double a,b,m;
    int n,x;
    cin>>n;
    for(int i=0;i<n;i++)
    { 
          cin>>a>>b;
          m=pow(a,b);
          x=(int)m%9907;
          cout<<m<<endl;
          
     }
     return 0;
}
        
        
       
 
